
图灵机 图灵机的变形 算法的定义
图灵机示例
~5 (E½C = {a
i
b
j
c
k
| i × j = k, i, j, j ≥ 1}TM)
对于收入字符串w:
1 从左至右扫描输入,确定Ù形式a
+
b
+
c
+
2 读写头返回带子的左端点
3 消去一个a,并向右扫描直到b出现。在b, c间来回移动,
成对消去b, c,直至把所有b消去(如果c全部消去以后还
有b,则拒绝)
4 如果还有a消去,则恢复所有消去的b,并重复第3步。
如果所有a都已经被消去,则检查所有c是否都已经被消
去。如果是则接收,否则拒绝。
吴 铤 杭州电子科技大学络空间安全学院
丘奇-ã(ØK